1. Field of the Invention
The present invention relates to techniques for performing error correction in data recording systems, and more particularly, to techniques for performing error correction with a decoder that uses a modular single recursion implementation.
2. Related Art
Errors in digital data can occur upon reading digital data stored on a data disk. Disk drives typically have error correction encoders and decoders that are used to detect and correct data errors. Error correction and detection can be performed using a Reed-Solomon (RS) code.
For each data symbol (byte), an RS encoder generates error correction check bytes. The check bytes are appending to the symbol to generate RS codewords, where N is number of symbols in each codeword. The RS codewords are then stored in memory (such as a magnetic hard disk) or transmitted over a communication channel.
After data is read from the memory, an RS decoder decodes the RS codewords to correct any errors. An RS decoder includes a syndrome computation block, a key-equation solver (KES) block, and a Chien search and error evaluator (CSEE) block. The syndrome computation block computes the syndromes, which are viewed as coefficients of a syndrome polynomial S(x). The syndromes are passed to the KES block.
If there are any non-zero syndromes, it is assumed that there is an error. The KES block solves equation (1) to determine the error locator polynomial V(x) and the error evaluator polynomial Q(x), where t is the number of errors that the RS code can correct.V(x)S(x)≡Q(x)mod x2t  (1)
The error locator and error evaluator polynomials are then passed to the CSEE block. The CSEE block calculates the error locations and the error values. The decoder can find the error locations by checking whether V(a−j)=0 for each j, 0≦j≦t−1. This process is called a Chien search. If V(a−j)=0, then each aj is one of the error locations. Each of the roots a−j of the error locator polynomial V(x) is the reciprocal of an error location. The error values ei are calculated using Forney's error value formula (2).
                              e          i                =                                                            Q                ⁡                                  (                  x                  )                                                                              V                  ′                                ⁡                                  (                  x                  )                                                      ❘            x                    =                      a                          -                              j                i                                                                        (        2        )            
In equation (2), V′(x) denotes the formal derivative of the error locator polynomial V(x). The CSEE block corrects the errors in the received word as it is being read out of the decoder by subtracting the error values ei from symbols at the found error locations in the received codeword.
The latency throughput bottleneck in RS decoders is in the KES block which solves equation (1). Typically, the critical path delay of the KES block determines the latency throughput of the decoder.
An Euclidean algorithm is an iterative approach for solving equation (1). For each successive value, the Euclidean algorithm iteratively determines the next error locator polynomial coefficients using the current and the previous error locator polynomial coefficients. The Euclidean algorithm also iteratively determines the next error evaluator polynomial coefficients using the current and the previous error evaluator polynomial coefficients.
Thus, the Euclidean algorithm performs two 2-term recursions to calculate the error locations and the error values. If each iteration is completed in one clock cycle, then as many as 2t clock cycles are needed to find the coefficients of the error-locator and error-evaluator polynomials. Because the syndrome polynomial S(x) has a degree 2t−1, and the other polynomials can have degrees as large as t, the algorithm needs to store roughly 6t field elements. As the latency of a sequential implementation is t2 cycles, which may be prohibitive, a parallel implementation, using 2t multipliers, is generally required.
It would however be desirable to provide techniques for decoding Reed-Solomon codewords that require less storage space and that achieve the parallel implementation latency using less multipliers.